/**
 * https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
 * 最小的k个数
 * @param arr
 * @param k
 */
const getLeastNumbers = (arr: number[], k: number): number[] => {
  // 边界判断
  if (arr.length === 0 || k === 0) return [];
  let len = arr.length;

  /**
   * 切分位置
   * @param s
   * @param e
   */
  const partition = (start: number, end: number) => {
    if (start === end) return start;
    // 将第一位作为参考点
    const pivot = arr[start];

    let s = start,
      e = end - 1;
    while (s < e) {
      // 从后往前, 如果找到了比pivot小的, 切换到到从前往后
      while (s < e) {
        if (arr[e] < pivot) {
          // 使用end的位置替换s的位置
          arr[s] = arr[e];
          break;
        }
        e--;
      }

      // 从前往后找, 如果找到了比pivot大的, 结束循环, 使用s替换end的元素
      while (s < e) {
        if (arr[s] > pivot) {
          arr[e] = arr[s];
          break;
        }
        s++;
      }
    }

    // 此时s(e)的位置就是pivot的位置
    arr[e] = pivot;
    return e;
  };

  /**
   * 快速排序
   * @param s
   * @param e
   */
  const quickSort = (s: number = 0, e: number = len): number[] => {
    const i = partition(s, e);
    if (i === k) return arr.slice(0, i);

    // 根据i判断是左切还是右切
    return i > k ? quickSort(s, e - 1) : quickSort(s + 1, e);
  };

  return quickSort();
};

const getLeastNumbers3 = (arr: number[], k: number): number[] => {
  // 边界判断
  if (arr.length === 0 || k === 0) return [];
  let len = arr.length;

  /**
   * 获取左孩子的索引
   * @param i
   * @returns
   */
  const getLeftIndex = (i: number) => (i << 1) + 1;

  /**
   * 获取有孩子的索引
   * @param i
   * @returns
   */
  const getRightIndex = (i: number) => (i << 1) + 2;

  /**
   * 获取左右孩子中比较小的
   * @param lI
   * @param rI
   */
  const getMin = (lI: number, rI: number) => {
    // 判断右孩子是否越界了, 直接返回左孩子
    if (rI >= len) return lI;
    return arr[lI] <= arr[rI] ? lI : rI;
  };

  /**
   * 交换两个元素
   * @param l
   * @param r
   */
  const swap = (l: number, r: number) => {
    const tmp = arr[l];
    arr[l] = arr[r];
    arr[r] = tmp;
  };

  /**
   * 下滤
   * @param i
   */
  const down = (i: number) => {
    // 只需要对非叶子结点处理
    const size = len >> 1;

    while (i < size) {
      // 获取左右子节点的索引
      const lI = getLeftIndex(i);
      const rI = getRightIndex(i);

      // 获取左右孩子中最小的孩子
      const minI = getMin(lI, rI);

      // 自己比孩子还要小, 直接结束
      if (getMin(minI, i) === i) return;

      // 自己和最小的孩子交换
      swap(i, minI);

      // 更新i, 继续进行交换
      i = minI;
    }
  };

  // 原地建堆, 从后往前
  const size = len >> 1;
  for (let i = size - 1; i >= 0; i--) {
    down(i);
  }

  const ans: number[] = [];
  // 不断的从堆顶取出k个元素
  for (let i = 0; i < k; i++) {
    ans.push(arr[0]);

    // 第一个元素和最后一个元素进行交换
    swap(0, --len);
    // 对第一个进行下滤
    down(0);
  }

  return ans;
};

const getLeastNumbers2 = (arr: number[], k: number): number[] => {
  // 边界判断
  if (arr.length === 0 || k === 0) return [];

  // 从小到大排序
  arr.sort((a, b) => a - b);

  return arr.slice(0, k);
};

// console.log(getLeastNumbers([5, 6, 2, 1, 9, 190, 3, 19, 30], 7));
console.log(getLeastNumbers([0, 0, 2, 3, 2, 1, 1, 2, 0, 4], 10));
